package com.qimingyu.linkedlist.doublelinkedlist;

/**
 * @version 1.0
 * @Author doreaxon
 * @Date 2023/8/26 21:17
 * @注释 带头尾哨兵的双向链表
 */
public class DoubleLinkedListWithGuard {

    /**
     * 创建一个内部类形式的结点类
     */
    static class Node {
        Node prev;//先驱结点
        int value;
        Node next;//后继节点

        Node(Node prev, Node next, int value) {
            this.prev = prev;
            this.next = next;
            this.value = value;
        }
    }

    private Node head;
    private Node tail;

    DoubleLinkedListWithGuard() {
        head = new Node(null, null, 666);//头哨兵
        tail = new Node(null, null, 999);//尾哨兵
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 找到指定位置的结点
     *
     * @param index
     * @return
     */
    Node findNode(int index) {
        Node p = head;//指针指向头哨兵
        int position = 0;
        while (p != tail && position <= index) {
            p = p.next;
            position++;
        }
        if (p == head || p == tail) {
            System.err.println("索引超出链表范围！程序终止！");
            System.exit(-1);
        }
        return p;
    }

    /**
     * 头插法
     *
     * @param value
     */
    public void addFirst(int value) {
        //创建一个新结点，prev指向头哨兵，next指向头哨兵的next
        Node inserted = new Node(head, head.next, value);
        //头哨兵的后继的前驱指向新节点
        head.next.prev = inserted;
        //头哨兵的后继指向新节点
        head.next = inserted;
    }

    /**
     * 删除头部节点
     */
    public void removeFirst() {
        //头节点的next指向头节点next的next
        head.next = head.next.next;
        //头结点的next的prev指向头结点（注意此时头节点的next已经改变）
        head.next.prev = head;
    }

    /**
     * 尾插法
     *
     * @param value
     */
    public void addLast(int value) {
        //创建一个新的结点前驱指向tail的前驱，后继指向tail
        Node inserted = new Node(tail.prev, tail, value);
        //tail的前驱的后继指向新节点
        tail.prev.next = inserted;
        //tail的前驱指向新结点
        tail.prev = inserted;
    }

    /**
     * 删除尾部结点
     */
    public void removeLast() {
        //tail的前驱的前驱的后继等于tail
        tail.prev.prev.next = tail;
        //tail的前驱等于tail的前驱的前驱
        tail.prev = tail.prev.prev;
    }

    /**
     * 指定位置插入节点
     *
     * @param index
     * @param value
     */
    public void insert(int index, int value) {
        //找到要插入位置原本的节点
        Node next = findNode(index);
        //新节点的前驱指向原结点的前驱，新节点的后继指向原节点
        Node inserted = new Node(next.prev, next, value);
        //原节点的前驱的后继指向新节点
        next.prev.next = inserted;
        //原节点的前驱指向新节点
        next.prev = inserted;
    }

    /**
     * 指定位置删除结点
     *
     * @param index
     */
    public void remove(int index) {
        //找到指定位置的节点
        Node node = findNode(index);
        //该结点的前驱的后继指向该节点的后继
        node.prev.next = node.next;
        //该节点的后继的前驱指向该节点的前驱
        node.next.prev = node.prev;
    }

    /**
     * 从后往前遍历
     */
    public void listFromHeadToTail() {
        Node p = head;
        while (p.next != tail) {
            p = p.next;
            System.out.print(p.value + " ");
        }
        System.out.println();
    }

    /**
     * 从前往后遍历
     */
    public void listFromTailToHead() {
        Node p = tail;
        while (p.prev != head) {
            p = p.prev;
            System.out.print(p.value + " ");
        }
        System.out.println();
    }

    /**
     * 递归遍历
     */
    public void recursionList() {
        recursion(head.next);
        System.out.println();
    }

    public void recursion(Node node) {
        if (node == tail) {
            return;
        }
        System.out.print(node.value + " ");
        recursion(node.next);
    }


    public static void main(String[] args) {
        DoubleLinkedListWithGuard doubleLinkedList = new DoubleLinkedListWithGuard();
        doubleLinkedList.addFirst(1);
        doubleLinkedList.addFirst(2);
        doubleLinkedList.addFirst(3);
        doubleLinkedList.addFirst(4);
        doubleLinkedList.addFirst(5);
        doubleLinkedList.addFirst(6);
        System.out.print("从前往后的遍历：");
        doubleLinkedList.listFromHeadToTail();
        System.out.print("从后往前的遍历：");
        doubleLinkedList.listFromTailToHead();
        System.out.println("索引位置为2的结点的value为：" + doubleLinkedList.findNode(2).value);
        doubleLinkedList.addLast(10);
        System.out.print("尾插法插入一个value为10的结点后的链表为：");
        doubleLinkedList.listFromHeadToTail();

        doubleLinkedList.removeFirst();
        System.out.print("移除一个头部结点后的链表为：");
        doubleLinkedList.listFromHeadToTail();

        doubleLinkedList.removeLast();
        System.out.print("移除一个尾部结点后的链表为：");
        doubleLinkedList.listFromHeadToTail();

        doubleLinkedList.insert(2, 0);
        System.out.print("在索引位置为2的地方添加一个value为0的结点后的链表为：");
        doubleLinkedList.listFromHeadToTail();

        doubleLinkedList.remove(1);
        System.out.print("在索引位置为1的地方删除一个结点后的链表为：");
        doubleLinkedList.listFromHeadToTail();

        System.out.print("递归遍历 ：");
        doubleLinkedList.recursionList();


        System.out.println("测试超出链表索引范围：");
        doubleLinkedList.insert(10, 10);

    }

}
